/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-08-19
 * Time: 18:41
 */
public class Test {
    //leetcode 76 最小覆盖字串
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        int[] hash1 = new int[128];
        int kinds = 0;
        for(char ch : t) {
            if(hash1[ch]++ == 0) kinds++;
        }
        int[] hash2 = new int[128];
        int begin = -1;
        int minlen = Integer.MAX_VALUE;
        for(int left = 0,right = 0,count = 0; right < s.length; right++) {
            char in = s[right];
            if(++hash2[in] == hash1[in]) count++;
            while(count == kinds) {
                if(right - left + 1 < minlen) {
                    begin = left;
                    minlen = right - left + 1;
                }
                char out = s[left++];
                if(hash2[out]-- == hash1[out]) count--;
            }
        }

        if(begin == -1) return new String();
        else return ss.substring(begin,begin + minlen);
    }
}
